#include <iostream>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
using namespace std;

//structure to store information about a variable
typedef struct VarInfo {
    int type;           //type (0 - int, 1 - float)
    float value;        //value
}VarInfo;

extern string current_function;     //String representing the currently executing function

class FuncDeclareStmt;  //Forward declare the FuncDeclareStmt class
class ReturnStmt;       //Forward declare the ReturnStmt class

//structure to store information about a function
typedef struct FunctionInfo {
    FuncDeclareStmt *body;              //Pointer to the function body
    map<string, VarInfo> symbol_table;  //The function symbol table
    string parent_function;             //The parent function
}FunctionInfo;

//Node in the AST
class Node {
public:
	Node() {}
	virtual ~Node() {}
	virtual float eval(map<string, FunctionInfo> &f) = 0;
	virtual int numChildren() {}
	virtual Node* getChild(int i) {}
};

//A statement
class Stmt : public Node {
    Stmt *next;
protected:
	virtual int numParts() = 0;
	virtual Node* getPart(int i) = 0;
public:
	Stmt();
	Stmt(Stmt* nextStmt) : next(nextStmt) { }
	virtual const char *getType() = 0;
	static Stmt* append(Stmt* a, Stmt* b);
	virtual float eval(map<string, FunctionInfo> &f) {
    }
	virtual void evalAll(map<string, FunctionInfo> &f) {
		eval(f);
        if (next != NULL) {
    		next->evalAll(f);
        }
	}
	Stmt* getNext() {
		return next;
	}
	Stmt* setNext(Stmt* nextStmt) {
		next = nextStmt;
	}
	
    virtual int numChildren() { return numParts() + 1; }
	virtual Node* getChild(int i) {
		if (i == numParts()) {
			return next;
		} else {
			return getPart(i);
		}
	}
	virtual bool isNull() {
		return false;
	}
};

//An expression
class Expr : public Stmt {
public:
	virtual const char *getType() {
        return "Expr";
    }
    int numParts() {
        return 1;
    }
	Node* getPart(int i) {
    }
};

//Atom - DataType, Identifier, Number, Arg, CallArg
class Atom : public Expr {
public:
	int numChildren() {
		return 0;
	}
	Node *getChild(int i) {
		return NULL;
	}
};

//Binary operation
class BinOp : public Expr {
public:
	Node *operand1_;
	Node *operand2_;

	int numChildren() {
		return 2;
	}

	Node* getChild(int i) {
		if (i == 1) {
			return operand1_;
		} else if (i == 2) {
			return operand2_;
		} else {
			return NULL;
		}
	}
};

//Data type (int = 0, float = 1)
class DataType : public Atom {
    int type_;      /* type = 0 -> int, type = 1 -> float */
public:
    DataType(string type = "");
    virtual float eval(map<string, FunctionInfo> &f);
    int getDataType() {
        return type_;
    }
};

//A number (int or float)
class Number : public Atom {
public:
	float value_;
	Number(float value = 0);
	virtual float eval(map<string, FunctionInfo> &f);
};

//An identifier
class Ident : public Atom {
public:
    string name_;
	Ident(string name = "");
    virtual const char *getType() { return "Ident"; }
	virtual float eval(map<string, FunctionInfo> &f);
};

//A single function declaration argument
class Arg : public Atom {
    int type_;
    Ident *argument_;
public:
    Arg(int type = 0, Ident *argument = NULL);
    virtual float eval(map<string, FunctionInfo> &f);
    int getArgType() {
        return type_;
    }
    Ident *getArgument() {
        return argument_;
    }
};

//A single function call argument
class CallArg : public Atom {
    Arg *arg_;
    Expr *expr_;
public:
    CallArg(Expr *expr);
    CallArg(Arg *arg, Expr *expr);
    virtual float eval(map<string, FunctionInfo> &f);
    Expr *getExpr() {
        return expr_;
    }
    Arg *getArg() {
        return arg_;
    }
    void setArg(Arg *arg) {
        this->arg_ = arg;
    }
};

//Binary operators : self explanatory
class Assign : public BinOp {
    bool check_exists_;
public:
    Assign(Node *operand1 = NULL, Node *operand2 = NULL, bool check_exists = true);
    virtual ~Assign() {delete operand1_; delete operand2_;}
    virtual float eval(map<string, FunctionInfo> &f);
};

class Times : public BinOp {
public:
	Times(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Times() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class And : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	And(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~And() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class Or : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Or(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Or() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};


class Modulus : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Modulus(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Modulus() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};


class Divide : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Divide(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Divide() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class Plus : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Plus(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Plus() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class Minus : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Minus(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Minus() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};


class Equals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Equals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Equals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class NotEquals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	NotEquals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~NotEquals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class Greater : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Greater(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Greater() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class GreaterEquals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	GreaterEquals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~GreaterEquals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class Less : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	Less(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~Less() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class LessEquals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	LessEquals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~LessEquals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class PlusEquals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	PlusEquals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~PlusEquals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

class MinusEquals : public BinOp {
	Node *operand1_;
	Node *operand2_;
public:
	MinusEquals(Node *operand1 = NULL, Node *operand2 = NULL);
	virtual ~MinusEquals() {delete operand1_; delete operand2_;}
	virtual float eval(map<string, FunctionInfo> &f);
};

//Null statement
class NullStmt : public Stmt {
protected:
	const char *getType() { return "null"; }
	int numParts() {
		return 0;
	}
	Node *getPart(int i) {
		return NULL;
	}
public:
    NullStmt() : Stmt(NULL) {
    }
	int numChildren() {
		return 0;
	}
	Node *getChild(int i) {
		return NULL;
	}
	bool isNull() {
		return true;
	}
	virtual float eval(map<string, FunctionInfo> &f) {
        return 1;
    }
};

//Function declaration arguments
class ArgStmt : public Stmt {
    Arg *head_arg_;
protected:
    const char *getType() { return "argslist";}
    int numParts() { return 1;}
    Node *getPart(int i) {
        return NULL;
        //return args_list_[i];
    }
    virtual float eval(map<string, FunctionInfo> &f) {
        /*map<string, VarInfo> &T = f[current_function].symbol_table;
        Stmt *temp = head_arg_;
        while (temp != NULL) {
            temp->eval(f);
            temp = temp->getNext();
        }*/
        return 1;
    }
public:
    ArgStmt(Arg *head_arg) : head_arg_(head_arg) {
    }
    Arg *getHeadArg() {
        return head_arg_;
    }
};

//Function call arguments
class CallArgStmt : public Stmt {
    CallArg *head_arg_;
protected:
    const char *getType(); 
    int numParts();
    Node *getPart(int i);
public:
    virtual float eval(map<string, FunctionInfo> &f);
    CallArgStmt(CallArg *head_arg);
    CallArg *getHeadArg();
};

//Function declaration statement
class FuncDeclareStmt : public Stmt {
public:
    DataType *return_type_;
    Ident *func_name_;
    ArgStmt *arguments_;
    Stmt *stmt_before_return_;
    ReturnStmt *return_stmt_;
    Stmt *stmt_after_return_;
    bool has_returned_;
    float return_value_;

protected:
    const char* getType();
    int numParts();
    Node *getPart(int i);
    virtual float eval(map<string, FunctionInfo> &f);
public:
    FuncDeclareStmt(DataType *rtype, Ident *name, ArgStmt *args, Stmt *stmt1, ReturnStmt *return_stmt, 
                    Stmt *stmt2);
};

//Function call statement
class FuncCall : public Expr {
public:
    string function_name_;
    CallArgStmt *callargs_;
    float return_value_;
protected:
    const char *getType();
    int numParts();
    Node *getPart(int i);
    virtual float eval(map<string, FunctionInfo> &f);
public:
    FuncCall(string function_name, CallArgStmt *callargs);
};

class ReturnStmt : public Stmt {
    Expr *expr_;
protected:
    const char* getType();
    int numParts();
    Node *getPart(int i);
public:
    virtual float eval(map<string, FunctionInfo> &f);
	virtual void evalAll(map<string, FunctionInfo> &f); 
    ReturnStmt(Expr *expr);
};


//Variable declaration statement
class DeclareStmt : public Stmt {
    DataType *type_;
    Assign *declare_atom_;

protected:
    const char* getType() { return "declare";}
    int numParts() { return 2;}
    Node *getPart(int i) {
        if (i == 1) {
            return type_;
        } else {
            return declare_atom_;
        }
    }
    virtual float eval(map<string, FunctionInfo> &f) {
        //cout << "declare : " << current_function << endl;
        map<string, VarInfo> &T = f[current_function].symbol_table;
        T[((Ident *)declare_atom_->operand1_)->name_].type = type_->getDataType();
        declare_atom_->eval(f);
    }
public:
    DeclareStmt(DataType *t, Assign *da) : type_(t), declare_atom_(da) {
    }
};

//Print statement
class Print : public Stmt {
    Expr *expr_;
protected:
    const char* getType() {return "print";}
    int numParts() { return 1;}
    Node *getPart(int i) {
        if (i == 1) {
            return expr_;
        }
    }
    virtual float eval(map<string, FunctionInfo> &f) {
        /*if (T.find(variable->name_) == T.end()) {
            cout << "No variable '" << variable->name_ << "' found in current scope" << endl;
            exit(-1);
        }*/
        //cout << "expr_->getType() = " << expr_->getType() << endl;
        cout << expr_->eval(f) << endl;
    }
public:
    Print(Expr *expr) : expr_(expr) {
    }
};


//If statement
class IfStmt : public Stmt {
private:
	Stmt *clause_;
	Stmt *ifblock_;
    Stmt *elseblock_;
protected:
	const char* getType();
	int numParts();
	Node *getPart(int i);
    virtual float eval(map<string, FunctionInfo> &f);
public:
	IfStmt(Stmt* e, Stmt* ifblock, Stmt *elseblock) : clause_(e), ifblock_(ifblock), elseblock_(elseblock) {
	}
};


//While statement
class WhileStmt : public Stmt {
private:
	Stmt *clause_;
    Stmt *block_;
protected:
	const char* getType();
	int numParts();
	Node *getPart(int i);
    virtual float eval(map<string, FunctionInfo> &f);
public:
	WhileStmt(Stmt* e, Stmt *block) : clause_(e), block_(block) {
	}
};


//For statement
class ForStmt : public Stmt {
private:
	Stmt *init_; 
    Stmt *condition_;
    Stmt *expr_;
    Stmt *block_;
protected:
	const char* getType();
	int numParts();
	Node *getPart(int i);
    virtual float eval(map<string, FunctionInfo> &f);
public:
	ForStmt(Stmt* init, Stmt *condition, Stmt *expr, Stmt *block) : 
            init_(init), condition_(condition), expr_(expr), block_(block) {
	}
};

